/**
 * @file     nextGreaterElement.js
 * @brief    [496. 下一个更大元素 I](https://leetcode.cn/problems/next-greater-element-i/)
 * @author   Zhu
 * @date     2024-11-28 10:35
 */

/**
 * O(mn)
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function (nums1, nums2) {
    const n1 = nums1.length;
    const n2 = nums2.length;
    const ans = [];

    for (let i = 0; i < n1; i++) {
        ans[i] = -1;
        let found = false;
        for (let j = 0; j < n2; j++) {
            if (nums2[j] === nums1[i]) {
                found = true;
                continue;
            }
            if (found) {
                if (nums2[j] > nums1[i]) {
                    ans[i] = nums2[j];
                    break;
                }
            }
        }
    }

    return ans;
};

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number[]}
 */
var nextGreaterElement = function (nums1, nums2) {
    const n1 = nums1.length;
    const n2 = nums2.length;
    const ans = [];

    const table = {}; // x -> y

    const stack = [];
    const top = () => nums2[stack[stack.length - 1]];
    for (let j = 0; j < n2; j++) {
        table[nums2[j]] = -1;
        while (nums2[j] > top()) {
            const i = stack.pop();
            table[nums2[i]] = nums2[j];
        }
        stack.push(j);
    }

    for (let i = 0; i < n1; i++) {
        ans[i] = table[nums1[i]];
    }

    return ans;
};
